﻿// 1301. 最大得分的路径数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>



using namespace std;
/*
https://leetcode.cn/problems/number-of-paths-with-max-score/

给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。
你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。
在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为：路径上所有数字的和。
请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回 [0, 0] 。


示例 1：
输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：
输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：
输入：board = ["E11","XXX","11S"]
输出：[0,0]


提示：
2 <= board.length == board[i].length <= 100
*/


class Solution {
public:
    vector<int> dp[150][150];
    vector<int> pathsWithMaxScore(vector<string>& board) {
        for (int i = 0; i < 150; i++) {
            for (int j = 0; j < 150; j++) {
                dp[i][j].push_back(0);
                dp[i][j].push_back(0);
            }
        }
        dp[0][0][1] = 1;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (i == 0 && j == 0) continue;
                if (board[i][j] == 'X') continue;
                int val = 0;
                if (i != board.size() - 1 || j != board[0].size() - 1) { val = board[i][j]-'0'; }
                int maxv = 0;
                if (i - 1 >=0 && j - 1 >=0) {
                    maxv = max(maxv, dp[i - 1][j - 1][0]+ val);
                }
                if (i - 1 >= 0) {
                    maxv = max(maxv, dp[i - 1][j][0]+ val);
                }
                if (j - 1 >= 0) {
                    maxv = max(maxv, dp[i][j-1][0]+ val);
                }
                
                if (i - 1 >= 0 && j - 1 >= 0 && maxv == dp[i - 1][j - 1][0]+val) {
                    dp[i][j][0] = maxv; dp[i][j][1] += dp[i - 1][j - 1][1];  dp[i][j][1] = dp[i][j][1] % 1000000007;
                }
                if (i - 1 >= 0 && maxv == dp[i - 1][j][0] + val) {
                    dp[i][j][0] = maxv; dp[i][j][1] += dp[i - 1][j][1]; dp[i][j][1] = dp[i][j][1] % 1000000007;
                }
                if (j - 1 >= 0 && maxv == dp[i][j - 1][0] + val) {
                    dp[i][j][0] = maxv; dp[i][j][1] += dp[i][j-1][1]; dp[i][j][1] = dp[i][j][1] % 1000000007;
                }
            }
        }
        if (dp[board.size() - 1][board[0].size() - 1][1] == 0) dp[board.size() - 1][board[0].size() - 1][0] = 0;
        return dp[board.size() - 1][board[0].size() - 1];
    }
};

int main()
{
    Solution s;

    vector<string> v = {
        "E11","XXX","11S"
    };

   s.pathsWithMaxScore(v);
}
 